package com.shm.meituan;

/**
 * 矩阵游戏
 * 时间限制： 3000MS
 * 内存限制： 589824KB
 * 题目描述：
 * 小美有一个2×2的矩阵，矩阵左上角、右上角、左下角、右下角的数字分别为0、A、B、C。
 *
 * 小美觉得该矩阵不够大，她按如下方法扩展该矩阵：
 *
 * 将2×2的矩阵扩展为4×4的矩阵，4×4的矩阵被分为左上角、右上角、左下角、右下角这4个2×2的矩阵，其中左上角为原2×2的矩阵，右上角为原2×2的矩阵每个位置上的数加上A，左下角为原2×2的矩阵每个位置上的数加上B，右下角为原2×2的矩阵每个位置上的数加上C；
 *
 * 将4×4的矩阵扩展为8×8的矩阵，8×8的矩阵被分为左上角、右上角、左下角、右下角这4个4×4的矩阵，其中左上角为原4×4的矩阵，右上角为原4×4的矩阵每个位置上的数加上A，左下角为原4×4的矩阵每个位置上的数加上B，右下角为原4×4的矩阵每个位置上的数加上C；
 *
 * ……
 *
 * 经过不断扩展，小美可以得到一个无穷大的矩阵。小美打算用该矩阵和小团玩游戏，即对小团进行N次提问，每次给出正整数X、Y，并问小团矩阵上第X行第Y列上的数是多少，由于该数可能很大，只要求小团回答该数除以10^9后的余数。
 *
 *
 *
 * 输入描述
 * 第一行输入四个由空格隔开的整数A、B、C和N（0<=A,B,C<10^9、1<=N<=10^5）。
 *
 * 接下来N行，每行输入两个由空格隔开的整数X和Y（1<=X,Y<=10^9）。
 *
 * 输出描述
 * 输出N行，每行输出一个整数，第i行输出第i次提问的答案，即矩阵对应位置上的数除以10^9后的余数。
 *
 *
 * 样例输入
 * 1 2 3 5
 * 3 3
 * 5 6
 * 6 1
 * 8 3
 * 8 8
 * 样例输出
 * 3
 * 4
 * 4
 * 7
 * 9
 *
 * 提示
 * 样例解释：
 * 扩展后的矩阵前8行和前8列如下：
 * 0 1 1 2 1 2 2 3
 * 2 3 3 4 3 4 4 5
 * 2 3 3 4 3 4 4 5
 * 4 5 5 6 5 6 6 7
 * 2 3 3 4 3 4 4 5
 * 4 5 5 6 5 6 6 7
 * 4 5 5 6 5 6 6 7
 * 6 7 7 8 7 8 8 9
 */
public class Main5 {
}
